import java.util.ArrayList;

/**
 * Created by L.jp
 * Description:如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
 * 我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
 * User: 86189
 * Date: 2022-07-14
 * Time: 23:46
 */
//数据流的数据不断更新，所以数据的排序也是不断更新的，没来一个数据就要更新新的顺序，所以采用插入排序符合这个
public class Solution {
    ArrayList<Integer> list=new ArrayList<>();
    public void Insert(Integer num) {
        if(list.isEmpty()){
            list.add( num );
        }else {
            //不是空就排序
            int i = 0;
            for (; i < list.size(); i++) {
                if ( num <= list.get( i ) ) {
                    break;
                }
            }
            list.add( i , num );
        }
    }
    
    public Double GetMedian() {
        int n=list.size();
        if(list.size()%2!=0){
            return (double)list.get( n/2 );
        }else{
            double a=list.get( n/2 );
            double b=list.get(n/2-1);
            return (double) (a+b)/2;
        }
    
    }
    
}
